package cn.qyd.kaoshi;

import java.util.Arrays;

/**
 * @author 邱运铎
 * @date 2024-03-30 20:47
 */
public class CoinsKind {
    private int[] m;

    public static void main(String[] args) {
        int target = 19;
//        int[] coins = new int[]{1,1,1};
        int[] coins = new int[]{2,4,8,10};
        CoinsKind coinsKind = new CoinsKind();
        int coins1 = coinsKind.minimumAddedCoins(coins, target);
        System.out.println(coins1);
    }

    public int minimumAddedCoins(int[] coins, int target) {
        m = new int[target + 1]; // 直接用m = new int[10005];也一样
        for (int c : coins) {
            m[c] += 1;
        }
        System.out.println(Arrays.toString(m));
        int s = 0;
        int a = 0;
        for (int i = 1; s < target; i++) {
            System.out.println("---s=" + s + "---m[i]=" + m[i] + "---i=" + i);
            s += i * m[i];
            System.out.println("---s=" + s + "---m[i]=" + m[i] + "---i=" + i);
            if (s < i) {
                s += i;
                a += 1;
            }
        }

        return a;
    }
}
